package com.xzz.finger;


/**
 * @author: hhz
 * @create: 2022-02-18 10:38
 * 剑指 Offer 14- I. 剪绳子
 **/
public class CuttingRope {
    public static void main(String[] args) {
        System.out.println(cuttingRope(2));
        System.out.println(cuttingRope(10));
        System.out.println(cuttingRope(120));
        System.out.println(cuttingRope(127));
    }
    public static int cuttingRope2(int n) {
        //定义dp数组，dp[i]表示长度为i的绳子剪成m端后长度的最大乘积(m>1)
        int dp[] = new int[n+1];
        dp[2]=1;
        for (int i = 3; i <= n; i++) {
            for (int j = 2; j < i; j++) {
                int max = Math.max(j * (i - j), j * dp[i - j]);
                dp[i] = Math.max(max,dp[i]);
            }
        }
        return dp[n];
    }
    public static int cuttingRope(int n){
        if(n<=3){
            return n-1;
        }
        long  res =1;
        while(n>4){
            res = res%1000000007;
            res = res*3;
            n-=3;
        }
        return (int)(res*n%1000000007) ;
    }
}
